/***************************************************************************************
/
/  Authors:
/           Ilan   Bar Magen  061220380	 ilanbm@t2
/    		Shalev Mintz      066078189  shalevmi@t2  
/
/  Submition date: 6/8/2008
/
/  This file contains:  A Deterministic Skip List class,
/						that has Ranking and indexing abilities (like a Ranked tree)
/						More details in the file.
/
/
/	/rank addon/		- this remark is embedded along the code,
/						  it is an indication for changes we made to give the skip list
/						  ranged ranking and indexing abilities
****************************************************************************************/


#ifndef DSL_H
#define DSL_H

#include<cstdlib>  // for NULL
#include<iostream>
#include "defenitions.h"

using namespace std;


// Skip_Node Class
// Class for containing single skip node data, for DRSkip_List class.
template <class D, class R, class K> //D - DataType, K - KeyType, R - accomulated type (for delta2)
class Skip_Node
{
public:   
	//why Public? and why this class is not nested to DRSkip_List?
	//Well... We've tried to make this class a nested one inside DRSkip_List, as it should be,
	//But the g++ (gcc) compailer didn't like it (aperantly this issue is a known bug in g++). 
	//Same for trying leting DRSkip_List be a friend of Skip_Node - g++ didn't liked it.
	//So we leave it public, as a simple C struct (but templated).
	//(besides, we believe in Socialism, private is for Capitalistic pigs)
	D data;		// Recommanded: to use a pointer, saving the real data outside dynamicly
	K key;		// Key record - has to be a comparable data type.
	int delta; /*rank addon*/ // delta is the skip distance for counting the index
	R delta2; /*rank addon*/ // delta2 is the the delta for the accumulated value of the nodes
	Skip_Node *right;	//right node
	Skip_Node *down;	//node below
	
	Skip_Node(K theKey = K(),	//default c'tor
		Skip_Node<D,R,K>* _right = NULL,
		Skip_Node<D,R,K>* _down  = NULL,
		const D& theData = D(),
		/*rank addon*/const int delta = 0,
		/*rank addon*/const R delta2 = R()):
	data(theData), key(theKey), right(_right), down(_down){}

	~Skip_Node() {} //D'tor. done member-wise, no dynamic allocations.
	// same for "Copy C'tor" and "Assign Op'r" 
};

// DRSkip_List Class
// Class for a skip list data structure which is implemented has a 
// Deterministic skip list, and has Ranking and indexing abilities (like a Ranked tree)
template <class D, class R, class K>
class DRSkip_List {
private: //might be protected, but in the current usage no need for protected,
	//no one who inherts it needs access to this data at this point. 
	const K INFINITY,	// a K type value that represet the "end" node key value
		NEG_INFINITY; // a K type value that represet the "start" node key value
	Skip_Node<D,R, K> *start, // start node
		*end;	// end node

	// "add_right_node", a protected method for adding a new node right to from_node
	// with the given values. returns a SL_RESULT type.
	SL_RESULT add_right_node(Skip_Node<D,R,K>* from_node ,
		const K theKey,
		/*rank addon*/const int distance,
			/*rank addon*/const R acc,
		const D& theData);


	// "delete_right_node", a protected method for deleting the node right to from_node
	SL_RESULT delete_right_node(Skip_Node<D,R,K>* from_node);

	// "Insert_Node_Rec", a protected method for inserting recursivly a node,
	// a helper function fro "Insert_Node"
	bool Insert_Node_Rec(const K theKey,
		Skip_Node<D,R,K>* from_node,
		const D& theData,
		/*rank addon*/const R acc,
		SL_RESULT* result = NULL);

	// "Remove_Node_Rec", a protected method for inserting recursivly a node,
	// a helper function fro "Remove_Node"
	bool Remove_Node_Rec(const K theKey, 
		Skip_Node<D,R,K>* from_node,
		/*rank addon*/const R acc,
		SL_RESULT* result = NULL);
	
	
	//"Node_By_Key" Returns pointer the node with "theKey" K type key.  /*rank addon*/
	Skip_Node<D,R,K>* Node_By_Key(const K theKey) const;		// O(logn)

	  // "delta2_By_Key", Return delta2 field of the node with "theKey" K type key.
	  R delta2_By_Key(const K theKey);									// O(logn)
	

	// "Update_Top_level", a helper function for Insert_Node and Remove_Node
	// for adding or removing the top level.
	SL_RESULT Update_Top_level();

	// "Ceil_Key", if exists returns the key, if not - returns closest one to follow
	K Ceil_Key(const K theKey) const;

	//"helper_Add_Accumulation_fromKey"
	//a helper function for "Add_Accumulation_fromKey"
	SL_RESULT helper_Add_Accumulation_fromKey(Skip_Node<D,R,K>* base_node, const K theKey, R acc) const;

public:
	DRSkip_List(const K& inf,const K& neg_inf):  //default c'tor
	  INFINITY(inf),
		  NEG_INFINITY(neg_inf)
	  {
		  end = new Skip_Node<D,R,K>(INFINITY);            // start(-inf) -> end(inf)
		  end->right = end;		                        //   |            /
		  /*rank addon*/end->delta = 1;					//  -inf --------/
		   /*rank addon*/end->delta2 = 0;					
		  start = new Skip_Node<D,R,K>(NEG_INFINITY,end);              
		  end->down = end;
		  /*rank addon*/start->delta = 1;
		  /*rank addon*/start->delta2 = 0;	
		  start->down = new Skip_Node<D,R,K>(*start);  //copy C'tor
	  } 

	  virtual ~DRSkip_List(){  //D'tor.
		  Skip_Node<D,R,K> *temp,*current = start,*cur_start = start->down;
		  delete start;
		  while(cur_start!=NULL) {
			  current = cur_start->right;
			  while(current!=end) {
				  temp = current;
				  current=current->right;
				  delete temp;
			  }
			  temp = cur_start;
			  cur_start=cur_start->down;
			  delete temp;
		  }
		  delete cur_start;
		  delete end;
	  }; 


	  // "Insert_Node", a public method for inserting a new node with a certain key and data
	  SL_RESULT Insert_Node(const K theKey,const D& theData = D());  // O(logn)

	  // "Remove_Node", a public method for Removing an existing node with a certain key and data
	  SL_RESULT Remove_Node(const K theKey);							// O(logn)

	  // "Data_By_Key", Return D type that is in the node where with "theKey" K type key.
	 D& Data_By_Key(const K theKey);									// O(logn)

	  // "Accumulated_By_Key", Return the accumulated delta2 value of the node with "theKey" K type key.
	  R Accumulated_By_Key(const K theKey) const;							// O(logn)

	  // "Index_By_Key", Return the index of the node with "theKey" K type key.
	  int Index_By_Key(const K theKey) const;							// O(logn)

	  // "Index_From_Base", Return the index of the node with "theKey" K type key from a given "base_node" node.
	  int Index_From_Base(Skip_Node<D,R,K>* base_node, const K theKey) const;	// O(logn)

	  //"Acc_From_Base", Return the accumulated value of delta2 till "theKey", from a given "base_node" node.
	  R Acc_From_Base(Skip_Node<D,R,K>* base_node, const K theKey) const;	// O(logn)


	  // "Key_By_Index", Return a K type Key value in the given index position node from the start
	  K Key_By_Index(const int index) const;							// O(logn)

	  // "Linked_List", Returns a pointer to the begining of the lowest level of the skip node,
	  // acctually giving access to a "Linked List" of the skiplist items.
	  Skip_Node<D,R,K>* Linked_List() const;							

	  // "For_Each_Node", Run a giving function on the data field in all nodes.
	  SL_RESULT For_Each_Node(SL_RESULT (*run_func)(D*));	


	  //"Add_Accumulation_fromKey", adds a new accumulated value of delta2 from "theKey"
	  SL_RESULT Add_Accumulation_fromKey(const K theKey, R acc) const;

	  //"Next_Key", Returns the following key
	  K Next_Key(const K theKey) const;

	  // print_skip - prints the skip-list - for debugging porpuse only
	  void print_skip(int inserted);
};

//For_Each_Node (Details in the Defenition of the class) 
template<class D, class R, class K>
SL_RESULT DRSkip_List<D,R,K>::For_Each_Node(SL_RESULT (*run_func)(D*))
{
	Skip_Node<D,R,K> *cur_right,*current = Linked_List();
	while(current!=end) {
		cur_right=current->right;
		SL_RESULT res = run_func(&(current->data));
		if(  res != SL_SUCCESS ) return res;
		current = cur_right;
	}
	return SL_SUCCESS;
}

//Linked_List (Details in the Defenition of the class) 
template<class D, class R, class K>
Skip_Node<D,R,K>* DRSkip_List<D,R,K>::Linked_List() const
{
	Skip_Node<D,R,K>* q = start;
	while(q->down != NULL) {q = q->down;}
	return q; // the anchor starting node at the bottom level of the skip list. 	

}

//Update_Top_level (Details in the Defenition of the class) 
template<class D, class R, class K>
SL_RESULT DRSkip_List<D,R,K>::Update_Top_level()
{
	if ((start->right != end)) // add another level?
	{
		Skip_Node<D,R,K>* new_start = new Skip_Node<D,R,K>(*start);
		new_start->down  = start;
		new_start->right = end;
		start = new_start;
	}

	if ((start->down->right == end) && (start->down->down != NULL) ) // remove top level? 
	{
		Skip_Node<D,R,K>* old_start = start; 
		start = start->down;
		delete old_start;
	}	
	return SL_SUCCESS;
}


//add_right_node (Details in the Defenition of the class) 
template<class D, class R, class K>
SL_RESULT DRSkip_List<D,R,K>::add_right_node(Skip_Node<D,R,K>* from_node ,
											const K theKey,
											/*rank addon*/const int distance,
											/*rank addon*/const R acc,
											const D& theData)
{
	Skip_Node<D,R,K>*  new_node = new Skip_Node<D,R,K>(*from_node);
	if(from_node->down != NULL)
	{
		new_node->down = from_node->down->right->right;
	}
	/*rank addon*/new_node->delta = distance;
	/*rank addon*/new_node->delta2 = acc;
	new_node->key = theKey;
	new_node->data = theData;
	from_node->right = new_node;
	return SL_SUCCESS;
}


//print_skip (Details in the Defenition of the class) 
template<class D, class R, class K>
void DRSkip_List<D,R,K>::print_skip(int inserted)
{
	Skip_Node<D,R,K>  *q,*c;
	q = start;
	c = start;
	cout << "=============================\n";
	while(c!=NULL){
	q = c;
	for(;q->key < 9999; q = q->right){
		for(int i=1;i<q->delta;i++) { cout << "---------"; }
		printf("(%3d|%3d)",q->key,q->delta2);
		}
		cout << "\n";
		c=c->down;
		}
	cout << "=============================\n";
}


//Key_By_Index (Details in the Defenition of the class)  /*rank addon*/
template<class D, class R, class K>
K DRSkip_List<D,R,K>::Key_By_Index(const int index) const
{
	Skip_Node<D,R,K> *q = start->down;
	int sum = -1; //starting from an anchor which is not counted 
	while(q != NULL)
	{
		while(q->right != end) 
		{
			if(sum + q->right->delta > index) break; 
			q = q->right;
			sum += q->delta;
		}
		if (sum == index) {return q->key;}
		q = q->down;
	}
	return end->key;
}

//Add_Accumulation_fromKey (Details in the Defenition of the class)  /*rank addon*/
template<class D, class R, class K>
SL_RESULT DRSkip_List<D,R,K>::Add_Accumulation_fromKey(const K theKey, R acc) const
{
	return helper_Add_Accumulation_fromKey(start->down,Ceil_Key(theKey),acc);
}

		template<class D, class R, class K>
		SL_RESULT DRSkip_List<D,R,K>::helper_Add_Accumulation_fromKey(Skip_Node<D,R,K>* base_node, const K theKey, R acc) const
		{
			 if(base_node == NULL || theKey == end->key) {
				return SL_SUCCESS;
		    	}
			while(base_node->right->key <= theKey) {
				base_node = base_node->right;
			}
			
			if(base_node->key == theKey) base_node->delta2 += acc;
			else base_node->right->delta2 += acc;
		
			return helper_Add_Accumulation_fromKey(base_node->down,theKey,acc);
		}


//Accumulated_By_Key (Details in the Defenition of the class)  /*rank addon*/
template<class D, class R, class K>
R DRSkip_List<D,R,K>::Accumulated_By_Key(const K theKey) const
{
	if (Node_By_Key(theKey) != end) return Acc_From_Base(start->down,theKey);  
	return R();
}

//Acc_From_Base (Details in the Defenition of the class)  /*rank addon*/
template<class D, class R, class K>
R DRSkip_List<D,R,K>::Acc_From_Base(Skip_Node<D,R,K>* base_node, const K theKey) const
{
	R sum = R();
	for(;base_node->right->key <= theKey; base_node = base_node->right) {
		sum+=base_node->right->delta2;
	}
	if(base_node->key == theKey) {
		return sum;
	}
	return sum + Acc_From_Base(base_node->down,theKey);
}


//Index_By_Key (Details in the Defenition of the class)  /*rank addon*/
template<class D, class R, class K>
int DRSkip_List<D,R,K>::Index_By_Key(const K theKey) const
{
	if (Node_By_Key(theKey) != end) return Index_From_Base(start->down,theKey)-1;  
	return -1;
}

//Index_From_Base (Details in the Defenition of the class)  /*rank addon*/
template<class D, class R, class K>
int DRSkip_List<D,R,K>::Index_From_Base(Skip_Node<D,R,K>* base_node, const K theKey) const
{
	int sum = 0;
	for(;base_node->right->key <= theKey; base_node = base_node->right) {
		sum+=base_node->right->delta;
	}
	if(base_node->key == theKey) {
		return sum;
	}
	return sum + Index_From_Base(base_node->down,theKey);
}


//Insert_Node (Details in the Defenition of the class)  
template<class D, class R, class K>
SL_RESULT DRSkip_List<D,R,K>::Insert_Node(const K theKey,const D& theData)
{
	SL_RESULT recursive_result = SL_SUCCESS;
	Insert_Node_Rec(theKey,start,theData,0,&recursive_result);
	//print_skip(theKey);
	return recursive_result;
}


//Insert_Node_Rec (Details in the Defenition of the class)  
template<class D, class R, class K>
bool DRSkip_List<D,R,K>::Insert_Node_Rec(const K theKey, 
									   Skip_Node<D,R,K>* from_node,
									   const D& theData,
									   	/*rank addon*/const R acc,
									   SL_RESULT* result)
{
	Skip_Node<D,R,K>  *q,*org_from;

	org_from = from_node;

	for(;from_node->right->key <= theKey; from_node = from_node->right);

	if(from_node->key == theKey) {
		*result = SL_EXISTS;
		return true; 
	}

	if(from_node->down == NULL) {
		add_right_node(from_node,theKey,1,acc,theData);
		// add checking if add_right_node failed
		*result = SL_SUCCESS;
		return true;
	}
	else
	{
		from_node->right->delta++;/*rank addon*/
		from_node->right->delta2+=acc;/*rank addon*/
	}

	//**** RECURSION CALL
	bool digger = Insert_Node_Rec(theKey, from_node->down, theData,/*rank addon*/acc, result); 
	//****

	if((*result != SL_SUCCESS) && (*result != SL_EXISTS)) {	
		return false; //get out from the recurstion
	}

	if(*result == SL_EXISTS) {	
		from_node->right->delta--;/*rank addon*/
		from_node->right->delta2-=acc;/*rank addon*/
	}

	if(digger == false) return false;

	q = from_node->down;
	from_node->right->delta = 0;/*rank addon*/
	from_node->right->delta2 = 0;/*rank addon*/
	for(;q->key != from_node->right->key;q = q->right) {
		from_node->right->delta += q->right->delta;/*rank addon*/
		from_node->right->delta2 += q->right->delta2;/*rank addon*/
	}


	q = from_node->down->right->right; //an insersion aquered on a deeper level  
	if(q->right->key < from_node->right->key) { //3 sons, need to add a new "building" in the middle.
		add_right_node(from_node, q->key,
						/*rank addon*/from_node->down->right->delta+q->delta/*rank addon*/,
						/*rank addon*/from_node->down->right->delta2+q->delta2/*rank addon*/,
						D());

		from_node->right->right->delta -= from_node->right->delta;/*rank addon*/
		from_node->right->right->delta2 -= from_node->right->delta2;/*rank addon*/
		if(org_from == start) Update_Top_level();
		return true;
	}
	return false;
}

//Ceil_Key   /*rank addon*/
template<class D, class R, class K>
K DRSkip_List<D,R,K>::Ceil_Key(const K theKey) const 
{
	Skip_Node<D,R,K>* current = start->down;
	if(theKey==end->key) return end->key;
	while(1){
		for(;current->right->key <= theKey; current = current->right);
		if(current->key == theKey) {
			return theKey;
		}
		if(current->down == NULL) {
			return current->right->key;
		}
		current = current->down;			
	}

}

//Next_Key   /*rank addon*/
template<class D, class R, class K>
K DRSkip_List<D,R,K>::Next_Key(const K theKey) const 
{
	int ceil_key = Ceil_Key(theKey);
	if (ceil_key > theKey) return ceil_key;
	int ceil_index = Index_By_Key(ceil_key);
	if (ceil_index != -1) return Key_By_Index(ceil_index+1);
	else return end->key;
}

//Node_By_Key Returns pointer the node with "theKey" K type key.  /*rank addon*/
template<class D, class R, class K>
Skip_Node<D,R,K>* DRSkip_List<D,R,K>::Node_By_Key(const K theKey) const 
{
	Skip_Node<D,R,K>* current = start->down;
	while(1){
		for(;current->right->key <= theKey; current = current->right);
		if(current->key == theKey) {
			while(current->down != NULL) current = current->down;
			return current;
		}
		if(current->down == NULL) {
			return end;
		}
		current = current->down;			
	}

}

//"delta2_By_Key" Return delta2 field of the node with "theKey" K type key. /*rank addon*/
template<class D, class R, class K>
R DRSkip_List<D,R,K>::delta2_By_Key(const K theKey)  
{
	return Node_By_Key(theKey)->delta2;
}

//Data_By_Key (Details in the Defenition of the class)  /*rank addon*/
template<class D, class R, class K>
D& DRSkip_List<D,R,K>::Data_By_Key(const K theKey)  
{
	return (Node_By_Key(theKey)->data);
}



//REMOVE NODE #######################################################


//delete_right_node (Details in the Defenition of the class) 
template<class D, class R, class K>
SL_RESULT DRSkip_List<D,R,K>::delete_right_node(Skip_Node<D,R,K>* from_node)
{
	Skip_Node<D,R,K>*  new_right = from_node->right->right;
	delete from_node->right;
	from_node->right = new_right; 
	return SL_SUCCESS; 

}

//Remove_Node (Details in the Defenition of the class) 
template<class D, class R, class K>
SL_RESULT DRSkip_List<D,R,K>::Remove_Node(const K theKey)
{
	//print_skip(theKey);
	SL_RESULT recursive_result = SL_SUCCESS;
	R delta_removed=delta2_By_Key(theKey);/*rank addon*/
	int index = Index_By_Key(theKey);
	int next_key = Key_By_Index(index+1);
	Remove_Node_Rec(theKey,start, /*rank addon*/delta_removed,&recursive_result);
	Update_Top_level(); //checks changes to top level
	//print_skip(theKey);
	if (next_key!=-1) Add_Accumulation_fromKey(next_key, delta_removed);
	return recursive_result; 
}

//Remove_Node_Rec (Details in the Defenition of the class) 
template<class D, class R, class K>
bool DRSkip_List<D,R,K>::Remove_Node_Rec(const K theKey, 
									   Skip_Node<D,R,K> *from_node,
									   /*rank addon*/const R acc,
									   SL_RESULT *result)
{ // 
	Skip_Node<D,R,K>  *q,*left_to_from,*last = from_node;

	for(;from_node->right->key < theKey; from_node = from_node->right){}; //Run Right to turning point on this level
	from_node->right->delta--;/*rank addon*/
	from_node->right->delta2-=acc;/*rank addon*/
	if (from_node->down == NULL) { // if it is the bottom
		if(from_node->right->key == theKey)  { //and if it is the key on the right
			from_node->right->down = start; //put a flag for deletion (is done in level above)
			*result = SL_SUCCESS;
			return true; //go to level above and procced
		}
		else // it is the bottom but no key....
		{
			from_node->right->delta++;/*rank addon*/
			from_node->right->delta2+=acc;/*rank addon*/
			*result = SL_NOT_EXISTS;
			return true; //pop out of the recursion
		}
	}

	//*********ACHTUNG!!!*********//
	//******RECURSION CALL!*******//
	//	  not recommended for	  //
	//    Pregnant women,		  //
	bool digger = Remove_Node_Rec(theKey, from_node->down,/*rank addon*/acc, result); //RECURSION CALL, go down level and procced
	//    and people who are	  //
	//    afraid of bugs.		  //
	//****************************//

	if((*result != SL_SUCCESS && *result != SL_NOT_EXISTS) || digger == false) {	
		return false; //pop out from the recurstion
	}

	if (*result == SL_NOT_EXISTS) {from_node->right->delta++;/*rank addon*/
									from_node->right->delta2+=acc;/*rank addon*/
									} 

	//print_skip(theKey);
	//Stage 1: continue level below job on current level.
	//==============================================================
	//CURRENT level block check
	//Check if current level nodes need to be updated or prepared for deletion in level above
	q = from_node->right;
	last = q;
	while(1) //run on current level
	{
		if(q->down->down == start || q->down == start) //if son is tagged for deletion, tag father too. like son like father.
		{							
			q->down = start;
			q->right->delta += q->delta; /*rank addon*/
			q->right->delta2 += q->delta2; /*rank addon*/
			q = q->right;
		}
		else
		{
			if(q->key != q->down->key) // if son has a new value, update father for the new value. an open minded father.
			{
				q->key = q->down->key;
				Skip_Node<D,R,K>* q2 = from_node->down;
				q->delta = 0;
				q->delta2 = 0;
				while(1) //runing on sons in block
				{	q2 = q2->right;
					q->delta += q2->delta;
					q->delta2 += q2->delta2;
					if (q2->key == q->key) break;					
				}

				//update right node's delta
				q->right->delta = 0;
				q->right->delta2 = 0;
				while(1) //runing on sons in block
				{	q2 = q2->right;
					q->right->delta += q2->delta;
					q->right->delta2 += q2->delta2;
					if (q2->key == q->right->key) break;					
				}

		
			}
			last = q; //update pointer to last node of the block
			break;
		}
	}

	//Stage 2: finish level below job on level below.
	//==============================================================
	//level BELOW block check
	//Check if current level nodes need to be deleted or updated from grandsons 
	left_to_from = from_node->down;
	q = from_node->down->right;

	while(q->key != last->key) 
	{
		if(q->down == start){ //yep. this son is executed. hmm... deleted.. yes..
			//q->right->addfromhere+ 
			q = q->right;
			delete_right_node(left_to_from); 
		}
		else
		{
			if(q->down != NULL && q->down->key != q->key) { //son, take the key from your grandson! don't lose the key!
				q->key = q->down->key;
			}
			q = q->right;
		}
		left_to_from = left_to_from->right;
	}

	// Stage 3: Decide stuff for level above (the calling recursion)
	//==============================================================
	// count the block in level below and operate.
	// 4 scenarios:
	// 1. 3 or 4 son-nodes in block:
	//			to make this block valid, we need to seperate it to two.
	//			take the second son-node and add a node to curent level connected to him.
	//				0------------0	TO---->		0-----0--------0
	//				0-0-0-0-(0)--0				0--0--0--0-(0)-0	() - optional
	// 2. block sized zero, and after it a block sized 2: (0 | 2 state)
	//			take the first son-node out of the two, and connect him to middle node in current level
	//			(make it a 1 | 1 state)
	//				0-0-------0	   TO---->		0----0-----0
	//				0-0--0-0--0					0-0--0--0--0	
	// 3. block sized zero, and after it a block sized 1: ( 0 | 1 state)
	//			no need for seperation, cancel the tail of the node that goes up.
	//				0-0----0	TO---->			0------0
	//				0-0-0--0					0-0-0--0	
	// 4. 1 or 2 son-nodes in block: no problem, nothing has to be done.
	q = from_node->down->right;
	int i = 0;
	for(;q->key != last->key;q = q->right) i++; // jenny count the block (don't be fooled by the bugs that i've got)
	if (i>=3) { //3 or 4 in the block
		add_right_node(from_node,from_node->down->right->right->key,0,0,D());
		from_node->right->down = from_node->down->right->right;
		from_node->right->delta = from_node->right->down->delta + from_node->down->right->delta ;/*rank addon*/
		from_node->right->delta2 = from_node->right->down->delta2 + from_node->down->right->delta2 ;/*rank addon*/
		last->delta -= from_node->right->delta;/*rank addon*/
		last->delta2 -= from_node->right->delta2;/*rank addon*/
		return true;
	}
	if (i==0) { // zero nodes between "buildings"
		if (from_node->down->right->right->right->key < from_node->right->right->key)
			// if there is 0|2, zero in first block and 2 in next block
		{ //then "change" the base of the "building" to the right one
			from_node->right->down = from_node->down->right->right;
			from_node->right->key = from_node->right->down->key;
			from_node->right->delta += from_node->right->down->delta;/*rank addon*/
			last->right->delta -= from_node->right->down->delta;/*rank addon*/
			from_node->right->delta2 += from_node->right->down->delta2;/*rank addon*/
			last->right->delta2 -= from_node->right->down->delta2;/*rank addon*/
		}
		else //only one in next block. no need for middle "building".
		{ // then demolish the building. destroy. eliminate. make it collaps.
			if (from_node->right != end) {
				last->right->delta += from_node->right->delta;/*rank addon*/
				last->right->delta2 += from_node->right->delta2;/*rank addon*/
				from_node->right->down = start; //node will be deleted in the calling recursion (level above)	
			}

		}
	}


	return true;
}


#endif //fin.
